package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @class Code45
 * @description 剑指 Offer 43. 1～n 整数中 1 出现的次数
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
 *
 * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 12
 * 输出：5
 * 示例 2：
 *
 * 输入：n = 13
 * 输出：6
 *  
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-08 10:27
 */
public class Code45 {

    public static void main(String[] args) {
        System.out.println(countDigitOne(10));
    }

    public static int countDigitOne(int n) {
        int digit = 1, low = 0, high = n / digit / 10, cur = n % 10, res = 0;
        while (low != n) {
            if (cur == 1) {
                res += low + 1 + high * digit;
            } else if (cur == 0) {
                res += high * digit;
            } else {
                res += (high + 1) * digit;
            }
            low = low + cur * digit;
            high /= 10;
            digit *= 10;
            cur = n / digit % 10;
        }
        return res;
    }

}

/*
递推式
拿1234举例
假设当前检查的位数是3
high = 12
low = 4
digit = 10
如果当前位数是 1 则 res += low + 1 + high * digit
如果当前位数是 0 则 res += high * digit
如果是其他数字，2~9 则 res += (high + 1) * digit
 */
